Problem

Time limit : 2sec / Memory limit : 256MB

题意简述：

给你一个有向图。如果$x \rightarrow y, y \rightarrow z$,加上$z \rightarrow x$。重复该过程直到不能再添加，求最终图中有多少边。

door♂

Solution

把方格$(i,j)$想象为一条边$i \rightarrow j $。
那么对于输入，可以得到一张有向图。

考虑用三种颜色给原图每个联通块染色。
令这三种颜色分别为$0,1,2$，且$0 \rightarrow 1 \rightarrow 2 \rightarrow 0$。

可以发现题目中的染色方法便是这张图上，若某个$0\rightarrow 1$且$1\rightarrow2$，则产生$2\rightarrow 0$的边。
那么在染色后，分为三种情况：

如果染色成功了，那么当前联通块对答案的贡献便是:所有$0$向$1$连边，所有$1$向$2$连边，所有$2$向$1$连边的总边数
如果不成功但是用了每种颜色，画图可知一定是出现了环（包括自环），于是这个联通块可以被连成一个完全图
如果不成功也没有使用每一种颜色，那么这个联通块的贡献就是输入的边

Code:

Click to show/hide the code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

typedef long long ll;
const int N = 5e5 + 9;

int n, m; 
ll to[N << 1], nxt[N << 1], beg[N], tot;
ll c[N], w[N << 1];
ll ans, f[4], flag;

inline void _read(int &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}

inline void add(const int &u, const int &v, const int &c)
{
	to[++tot] = v;
	nxt[tot] = beg[u];
	w[tot] = c;
	beg[u] = tot;
}

inline void dfs(int u)
{
	f[c[u]]++;
	for (register int i = beg[u]; i; i = nxt[i])
	{
		if (w[i] == 1)f[3]++;
		if (!(~c[to[i]]))
		{
			c[to[i]] = (c[u] + w[i]) % 3;
			dfs(to[i]);
		}
		else if (c[to[i]] != (c[u] + w[i]) % 3)
			flag = 1;
	}
}

int main()
{
	_read(n), _read(m);
	for (register int i = 1, u, v; i <= m; i++)
	{
		_read(u), _read(v);
		add(u, v, 1), add(v, u, 2);
	}

	memset(c, -1, sizeof c);
	for (register int i = 1; i <= n; i++)
		if (!(~c[i]))
		{
			f[c[i] = 0] = f[1] = f[2] = f[3] = flag = 0;
			dfs(i);
			if (flag)
			{
				register ll cnt = f[0] + f[1] + f[2];
				ans += cnt * cnt;
				continue;
			}
			if ((!f[0]) || (!f[1]) || (!f[2]))
			{
				ans += f[3];
				continue;
			}

			ans += f[0] * f[1];
			ans += f[1] * f[2];
			ans += f[2] * f[0];
		}

	printf("%lld", ans);
	return 0;
}